{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Profit of Operating a Centennial Wheel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperationsMaxProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #经营摩天轮的最大利润"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在经营一座摩天轮，该摩天轮共有 <strong>4 个座舱</strong> ，每个座舱<strong> 最多可以容纳 4 位游客</strong> 。你可以 <strong>逆时针</strong>&nbsp;轮转座舱，但每次轮转都需要支付一定的运行成本 <code>runningCost</code> 。摩天轮每次轮转都恰好转动 1 / 4 周。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的数组 <code>customers</code> ， <code>customers[i]</code> 是在第 <code>i</code> 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 <code>i</code> 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 <code>boardingCost</code> ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。</p>\n",
    "\n",
    "<p>你可以随时停下摩天轮，即便是 <strong>在服务所有游客之前</strong> 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，<strong>将免费进行</strong><strong>所有后续轮转</strong>&nbsp;。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 <strong>下一次轮转</strong> 。</p>\n",
    "\n",
    "<p>返回最大化利润所需执行的 <strong>最小轮转次数</strong> 。 如果不存在利润为正的方案，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/26/wheeldiagram12.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>customers = [8,3], boardingCost = 5, runningCost = 6\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>座舱上标注的数字是该座舱的当前游客数。\n",
    "1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。\n",
    "2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。\n",
    "3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。\n",
    "轮转 3 次得到最大利润，最大利润为 $37 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>customers = [10,9,6], boardingCost = 6, runningCost = 4\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。\n",
    "2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。当前利润为 8 * $6 - 2 * $4 = $40 。\n",
    "3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。\n",
    "4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。\n",
    "5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。\n",
    "6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。\n",
    "7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。\n",
    "轮转 7 次得到最大利润，最大利润为$122 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。\n",
    "2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 2 * $92 = -$177 。\n",
    "3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。\n",
    "4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 11 * $1 - 4 * $92 = -$357 。\n",
    "5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。\n",
    "利润永不为正，所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == customers.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= customers[i] &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= boardingCost, runningCost &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-profit-of-operating-a-centennial-wheel](https://leetcode.cn/problems/maximum-profit-of-operating-a-centennial-wheel/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-profit-of-operating-a-centennial-wheel](https://leetcode.cn/problems/maximum-profit-of-operating-a-centennial-wheel/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,3]\\n5\\n6', '[10,9,6]\\n6\\n4', '[3,4,0,5,1]\\n1\\n92']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        # 满人时转一次的收益\n",
    "        full_cost = boardingCost << 2\n",
    "        # 血亏摩天轮，赶紧润\n",
    "        if runningCost >= full_cost:\n",
    "            return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        mx = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += full_cost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "        if wait > 0:    # 没人会来了\n",
    "            full, wait = divmod(wait, 4)    \n",
    "            i += full   # 满座的时候无脑转\n",
    "            profit += full * (full_cost - runningCost)\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "            # 剩下的人如果赚，那就转到底\n",
    "            profit += wait * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                ans = i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "\n",
    "        profit = 0\n",
    "        cnt = -1\n",
    "        cur = 0\n",
    "        acc = 0\n",
    "        n = len(customers)\n",
    "        i = 1\n",
    "        while i<=n:\n",
    "            cur += customers[i-1]\n",
    "            if cur >= 4:\n",
    "                cur -= 4\n",
    "                acc += 4\n",
    "                cp = boardingCost * (acc) - runningCost * i\n",
    "                if cp > profit:\n",
    "                    profit = cp\n",
    "                    cnt = i\n",
    "            else:\n",
    "                acc += cur\n",
    "                cur = 0\n",
    "                cp = boardingCost * (acc) - runningCost * i\n",
    "                if cp > profit:\n",
    "                    profit = cp\n",
    "                    cnt = i\n",
    "            i += 1\n",
    "        while cur > 0:\n",
    "            if cur >= 4:\n",
    "                cur -= 4\n",
    "                acc += 4\n",
    "                cp = boardingCost * (acc) - runningCost * i\n",
    "                if cp > profit:\n",
    "                    profit = cp\n",
    "                    cnt = i\n",
    "            else:\n",
    "                acc += cur\n",
    "                cur = 0\n",
    "                cp = boardingCost * (acc) - runningCost * i\n",
    "                if cp > profit:\n",
    "                    profit = cp\n",
    "                    cnt = i\n",
    "            i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        ans = -1\n",
    "        ceil = i = wait = cur = t = 0\n",
    "        n = len(customers)\n",
    "        while wait or i < n:\n",
    "            wait += customers[i] if i < n else 0\n",
    "            i += 1\n",
    "            up = wait if wait < 4 else 4\n",
    "            wait -= up\n",
    "            t += 1\n",
    "            cur += up*boardingCost - runningCost\n",
    "            if cur > ceil:\n",
    "                ceil = cur\n",
    "                ans = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        waiting, profit, ret, retv = 0, 0, 1145141919810, -1145141919810\n",
    "        i = 0\n",
    "        for v in customers:\n",
    "            waiting += v\n",
    "            up = min(waiting, 4)\n",
    "            waiting -= up\n",
    "            profit += up * boardingCost - runningCost\n",
    "            if profit > retv:\n",
    "                retv = profit\n",
    "                ret = i\n",
    "            i += 1\n",
    "        while waiting:\n",
    "            up = min(waiting, 4)\n",
    "            waiting -= up\n",
    "            profit += up * boardingCost - runningCost\n",
    "            if profit > retv:\n",
    "                retv = profit\n",
    "                ret = i\n",
    "            i += 1\n",
    "\n",
    "        return ret + 1 if retv > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        n = len(customers)\n",
    "        max_profit, cur_profit = 0,0\n",
    "        best_cot = -1\n",
    "        i = 0\n",
    "        remain = 0\n",
    "        while i<n or remain>0:\n",
    "            if i<n:\n",
    "                remain += customers[i]\n",
    "            play_num = min(4, remain)\n",
    "            remain -= play_num\n",
    "            cur_profit += (play_num*boardingCost - runningCost)\n",
    "            if cur_profit>max_profit:\n",
    "                max_profit = cur_profit\n",
    "                best_cot = i+1\n",
    "            i+=1\n",
    "        return best_cot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        # 满人时转一次的收益（不计成本）\n",
    "        full_cost = boardingCost << 2\n",
    "        # 血亏摩天轮，赶紧润\n",
    "        if runningCost >= full_cost: return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        max_profit = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += full_cost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > max_profit:\n",
    "                max_profit = profit\n",
    "                ans = i\n",
    "        if wait > 0:\n",
    "            full, wait = divmod(wait, 4)    \n",
    "            i += full\n",
    "            profit += full * (full_cost - runningCost)\n",
    "            if profit > max_profit:\n",
    "                max_profit = profit\n",
    "                ans = i\n",
    "            # 剩下的人如果赚，那就转到底\n",
    "            profit += wait * boardingCost - runningCost\n",
    "            if profit > max_profit:\n",
    "                ans = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        acc_customers, i = customers[0], 1\n",
    "        total_aboard = 0\n",
    "        max_inte, max_iter = 0, -1\n",
    "        while acc_customers > 0 or i < len(customers):\n",
    "            aboard = min(4, acc_customers)\n",
    "            acc_customers -= aboard\n",
    "            total_aboard += aboard\n",
    "            interest = total_aboard * boardingCost - i * runningCost\n",
    "            if interest > max_inte:\n",
    "                max_inte = interest\n",
    "                max_iter = i\n",
    "            if i < len(customers):\n",
    "                acc_customers += customers[i]\n",
    "            i += 1\n",
    "        return max_iter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        curnum = 0\n",
    "        curtimes = 0\n",
    "        res = 0\n",
    "        maxmoney = 0\n",
    "        i = 0\n",
    "        temp_money = 0\n",
    "        if boardingCost*4 <= runningCost:\n",
    "            return -1\n",
    "        while i < len(customers) or curnum:\n",
    "            if i < len(customers):\n",
    "                curnum += customers[i]\n",
    "                \n",
    "            if curnum < 4:\n",
    "                temp_money +=  curnum * boardingCost - runningCost\n",
    "                curtimes += 1\n",
    "                curnum = 0\n",
    "            else:\n",
    "                curtimes += 1\n",
    "                temp_money += 4 * boardingCost - runningCost\n",
    "                curnum -= 4\n",
    "            if temp_money > maxmoney:\n",
    "                maxmoney = temp_money\n",
    "                res = curtimes\n",
    "            i += 1\n",
    "        if maxmoney:\n",
    "            return res\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        max_val = 0\n",
    "        max_step = -1\n",
    "        money = 0\n",
    "        wait = 0\n",
    "        i = 0\n",
    "        while i < len(customers) or wait > 0:\n",
    "            people = customers[i] if i < len(customers) else 0\n",
    "            money -= runningCost\n",
    "            wait += people\n",
    "            if wait >= 4:\n",
    "                money += boardingCost * 4\n",
    "                wait -= 4\n",
    "                if money > max_val:\n",
    "                    max_val = money\n",
    "                    max_step = i + 1\n",
    "            elif wait > 0:\n",
    "                money += boardingCost * wait\n",
    "                wait = 0\n",
    "                if money > max_val:\n",
    "                    max_val = money\n",
    "                    max_step = i + 1\n",
    "            i += 1\n",
    "        return max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        if runningCost >= boardingCost << 2:\n",
    "            return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        mx = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += 4 * boardingCost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "        if wait > 0:    # 没人会来了\n",
    "            full, wait = divmod(wait, 4)    # 满座的时候无脑转\n",
    "            profit += full * (boardingCost * 4 - runningCost)\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i + full\n",
    "            # 剩下的人如果赚，答案+1\n",
    "            profit += wait * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                ans = i + full + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        if runningCost >= boardingCost << 2:\n",
    "            return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        mx = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += 4 * boardingCost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "        if wait > 0:    # 没人会来了\n",
    "            full, wait = divmod(wait, 4)    # 满座的时候无脑转\n",
    "            i += full\n",
    "            profit += full * (boardingCost * 4 - runningCost)\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "            # 剩下的人如果赚，答案+1\n",
    "            profit += wait * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                ans = i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        ans = -1\n",
    "        mx = t = 0\n",
    "        wait = 0\n",
    "        i = 0\n",
    "        while wait or i < len(customers):\n",
    "            wait += customers[i] if i < len(customers) else 0\n",
    "            up = wait if wait<4 else 4\n",
    "            wait -= up\n",
    "            t += up*boardingCost - runningCost\n",
    "            i += 1\n",
    "            if t > mx:\n",
    "                mx = t\n",
    "\n",
    "                ans = i\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        # 满人时转一次的收益\n",
    "        full_cost = boardingCost << 2\n",
    "        # 血亏摩天轮，赶紧润\n",
    "        if runningCost >= full_cost:\n",
    "            return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        mx = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += full_cost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "        if wait > 0:    # 没人会来了\n",
    "            full, wait = divmod(wait, 4)    \n",
    "            i += full   # 满座的时候无脑转\n",
    "            profit += full * (full_cost - runningCost)\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "            # 剩下的人如果赚，那就转到底\n",
    "            profit += wait * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                ans = i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        if runningCost >= boardingCost << 2:\n",
    "            return -1\n",
    "        \n",
    "        wait = 0    # 等待的游客数量\n",
    "        profit = 0  # 利润\n",
    "        mx = 0      # 历史最高利润\n",
    "        ans = -1    # 历史最高利润的旋转次数\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            wait += c\n",
    "            profit -= runningCost\n",
    "            if wait >= 4:\n",
    "                profit += 4 * boardingCost\n",
    "                wait -= 4\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i\n",
    "        if wait > 0:    # 没人会来了\n",
    "            full, wait = divmod(wait, 4)    # 满座的时候无脑转\n",
    "            profit += full * (boardingCost * 4 - runningCost)\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i + full\n",
    "            # 剩下的人如果赚，答案+1\n",
    "            if wait * boardingCost > runningCost:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        ans = -1\n",
    "        mx = t = 0\n",
    "        wait = 0\n",
    "        i = 0\n",
    "        while wait or i < len(customers):\n",
    "            wait += customers[i] if i < len(customers) else 0\n",
    "            up = wait if wait < 4 else 4\n",
    "            wait -= up\n",
    "            t += up * boardingCost - runningCost\n",
    "            i += 1\n",
    "            if t > mx:\n",
    "                mx = t\n",
    "                ans = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        res, sm, p, bni, index = 0, 0, 0, 4*boardingCost - runningCost, -2\n",
    "        if bni <= 0: return -1\n",
    "        for i,v in enumerate(customers):\n",
    "            p += v\n",
    "            if p < 4: sm, p = sm + boardingCost*p - runningCost, 0\n",
    "            else: sm, p = sm + bni, p - 4\n",
    "            if sm > res: index, res = i, sm\n",
    "        np, p = divmod(p,4)\n",
    "        tep, sm = p*boardingCost - runningCost, sm + np * bni\n",
    "        if tep > 0: sm, np = sm + tep, np + 1\n",
    "        return index + 1 if sm <= res else len(customers) + np\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        times = 0\n",
    "        mn_times = 0\n",
    "        cnt = 0\n",
    "        for i, customer in enumerate(customers):\n",
    "            cnt += customer\n",
    "            ans += min(4, cnt)*boardingCost\n",
    "            ans -= runningCost\n",
    "            cnt -= min(4, cnt)\n",
    "            times+=1\n",
    "            if ans > res:\n",
    "                res = ans\n",
    "                mn_times = times\n",
    "        while(cnt>0):\n",
    "            ans += min(4, cnt)*boardingCost\n",
    "            ans -= runningCost\n",
    "            cnt -= min(cnt, 4)\n",
    "            times+=1\n",
    "            if ans > res:\n",
    "                res = ans\n",
    "                mn_times = times\n",
    "        return mn_times if ans>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:       \n",
    "        ans = -1\n",
    "\n",
    "        if boardingCost * 4 <= runningCost:\n",
    "            return ans\n",
    "\n",
    "        while customers and customers[-1] == 0:\n",
    "            customers.pop()\n",
    "\n",
    "        cnt = profit = mx = 0\n",
    "        for i, c in enumerate(customers):\n",
    "            cnt += c \n",
    "            avails = min(cnt, 4)\n",
    "            profit += avails * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i+1\n",
    "            cnt -= avails\n",
    "        \n",
    "        a,b = divmod(cnt, 4)\n",
    "        profit += (4 * boardingCost - runningCost) * a\n",
    "        if profit > mx:\n",
    "            mx = profit\n",
    "            ans = len(customers) + a\n",
    "\n",
    "        profit += b * boardingCost - runningCost\n",
    "        if profit > mx:\n",
    "            mx = profit\n",
    "            ans = len(customers) + a + 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:       \n",
    "        ans = -1\n",
    "\n",
    "        if boardingCost * 4 <= runningCost:\n",
    "            return ans\n",
    "\n",
    "        cnt = profit = mx = 0\n",
    "        for i, c in enumerate(customers):\n",
    "            cnt += c \n",
    "            avails = min(cnt, 4)\n",
    "            profit += avails * boardingCost - runningCost\n",
    "            if profit > mx:\n",
    "                mx = profit\n",
    "                ans = i+1\n",
    "            cnt -= avails\n",
    "        \n",
    "        a,b = divmod(cnt, 4)\n",
    "        profit += (4 * boardingCost - runningCost) * a\n",
    "        if profit > mx:\n",
    "            mx = profit\n",
    "            ans = len(customers) + a\n",
    "\n",
    "        profit += b * boardingCost - runningCost\n",
    "        if profit > mx:\n",
    "            mx = profit\n",
    "            ans = len(customers) + a + 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        ans = -1\n",
    "        mx = t = 0\n",
    "        wait = 0\n",
    "        i = 0\n",
    "        while wait or i < len(customers):\n",
    "            wait += customers[i] if i < len(customers) else 0\n",
    "            up = wait if wait < 4 else 4\n",
    "            wait -= up\n",
    "            t += up * boardingCost - runningCost\n",
    "            i += 1\n",
    "            if t > mx:\n",
    "                mx = t\n",
    "                ans = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        n = len(customers)\n",
    "        ans = -1\n",
    "        tm = -1\n",
    "        profit = 0\n",
    "        people = 0\n",
    "        i = 0\n",
    "        while i < n or people:\n",
    "            if i < n:\n",
    "                people += customers[i]\n",
    "\n",
    "            add = 4 if people > 4 else people\n",
    "            people -= add\n",
    "            profit += add * boardingCost\n",
    "            profit -= runningCost\n",
    "            if profit > ans:\n",
    "                ans = profit\n",
    "                tm = i\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return tm + 1 if ans > 0 else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        r = 0\n",
    "        max_r = 0\n",
    "        term = -1\n",
    "        left_cus = 0\n",
    "        c_i = 0\n",
    "        term_count = 0\n",
    "        while left_cus>0 or c_i<len(customers):\n",
    "            term_count+=1\n",
    "            if c_i<len(customers):\n",
    "                left_cus+=customers[c_i]\n",
    "                c_i+=1\n",
    "            if left_cus<4:\n",
    "                r += boardingCost*left_cus-runningCost\n",
    "                left_cus=0\n",
    "            else:\n",
    "                r += boardingCost*4-runningCost\n",
    "                left_cus-=4\n",
    "            \n",
    "            if r>0 and max_r<r:\n",
    "                term = term_count\n",
    "                max_r = r\n",
    "        return term\n",
    "\n",
    "\n",
    "                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        upnum = 0\n",
    "        maxprofit = -999999999999999\n",
    "        profit = 0\n",
    "        wait = 0\n",
    "        res = -1\n",
    "        for arrive in customers:\n",
    "            wait += arrive\n",
    "            if wait > 4:\n",
    "                wait -= 4\n",
    "                profit += 4 * boardingCost\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            upnum += 1\n",
    "            profit -= runningCost\n",
    "            if profit > maxprofit:\n",
    "                maxprofit = profit\n",
    "                res = upnum\n",
    "            print(arrive, wait, profit)\n",
    "        # print('---------------')\n",
    "        while wait:\n",
    "            if wait > 4:\n",
    "                wait -= 4\n",
    "                profit += 4 * boardingCost\n",
    "            else:\n",
    "                profit += wait * boardingCost\n",
    "                wait = 0\n",
    "            upnum += 1\n",
    "            profit -= runningCost\n",
    "            if profit > maxprofit:\n",
    "                maxprofit = profit\n",
    "                res = upnum\n",
    "            # print(arrive, wait, profit)\n",
    "\n",
    "        if profit <= 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        # 先看看单圈利润是否为正    \n",
    "        if boardingCost * min(4, sum(customers)) - runningCost <= 0:    return -1\n",
    "        \n",
    "        rest = 0        # 当前剩余等待人数，大于等于4则4个人上车，小于4则有多少人上多少人\n",
    "        times = 0       # 获得最大盈利需要运转的圈数\n",
    "\n",
    "        while customers[-1] == 0:\n",
    "            customers.pop(-1)\n",
    "\n",
    "        for customer in customers:\n",
    "            rest = max(rest + customer - 4, 0)\n",
    "            times += 1\n",
    "\n",
    "        t, l = divmod(rest, 4)\n",
    "        return times + t + (1 if l * boardingCost > runningCost else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        ans = -1\n",
    "        mx = t = 0\n",
    "        wait = 0\n",
    "        i = 0\n",
    "        while wait or i < len(customers):\n",
    "            wait += customers[i] if i < len(customers) else 0\n",
    "            up = wait if wait < 4 else 4\n",
    "            wait -= up\n",
    "            t += up * boardingCost - runningCost\n",
    "            i += 1\n",
    "            if t > mx:\n",
    "                mx = t\n",
    "                ans = i\n",
    "        return ans\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/maximum-profit-of-operating-a-centennial-wheel/solutions/2147935/python3javacgo-yi-ti-yi-jie-mo-ni-by-lcb-6kz7/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        # 先看看单圈利润是否为正    \n",
    "        if boardingCost * min(4, sum(customers)) - runningCost <= 0:    return -1\n",
    "        \n",
    "        rest = 0        # 当前剩余等待人数，大于等于4则4个人上车，小于4则有多少人上多少人\n",
    "        times = 0       # 获得最大盈利需要运转的圈数\n",
    "\n",
    "        while customers[-1] == 0:\n",
    "            customers.pop(-1)\n",
    "            \n",
    "        for customer in customers:\n",
    "            rest = max(rest + customer - 4, 0)\n",
    "            times += 1\n",
    "\n",
    "        t, l = divmod(rest, 4)\n",
    "        if l * boardingCost > runningCost:\n",
    "            return times + t + 1\n",
    "        else:\n",
    "            return times + t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        k = len(customers)\n",
    "        cnt = 0\n",
    "        if 4*boardingCost-runningCost<=0:\n",
    "            return -1\n",
    "\n",
    "        for i in range (0,k):\n",
    "            if i==k-1:\n",
    "                if customers[i] >= 4:\n",
    "                    cnt = cnt + floor(customers[i]/4)\n",
    "                    if (customers[i]%4)*boardingCost-runningCost >0:\n",
    "                        cnt = cnt + 1\n",
    "                        return cnt\n",
    "                    else:\n",
    "                        return cnt\n",
    "                else:\n",
    "                    if customers[i]*boardingCost-runningCost >0:\n",
    "                        return cnt+1\n",
    "                    else:\n",
    "                        if cnt > 0:\n",
    "                            return cnt\n",
    "                        else: \n",
    "                            return -1\n",
    "\n",
    "            else:\n",
    "                if customers[i] >= 4:\n",
    "                    cnt += 1\n",
    "                    customers[i+1]=customers[i+1]+customers[i]-4\n",
    "                else:\n",
    "                    '''if (customers[i]*boardingCost-runningCost)>0:\n",
    "                        cnt +=1\n",
    "                    else: \n",
    "                        continue'''\n",
    "                    cnt += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        n=len(customers)\n",
    "        profit=[]\n",
    "        cp=0\n",
    "        for i in range(n-1):\n",
    "            cp-=runningCost\n",
    "            if customers[i]>4:\n",
    "                customers[i+1]+=customers[i]-4\n",
    "                customers[i]=4\n",
    "            cp+=customers[i]*boardingCost\n",
    "            profit.append(cp)\n",
    "        leftc=customers[n-1]\n",
    "        while leftc>0:\n",
    "            cp-=runningCost\n",
    "            if leftc<=4:               \n",
    "                cp+=leftc*boardingCost\n",
    "                profit.append(cp)\n",
    "                leftc=0\n",
    "            else:\n",
    "                leftc-=4               \n",
    "                cp+=4*boardingCost\n",
    "                profit.append(cp)\n",
    "               \n",
    "        mp=max(profit)\n",
    "        # print(profit)\n",
    "        if mp<=0:\n",
    "            return -1\n",
    "        return profit.index(mp)+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: list[int], boardingCost: int, runningCost: int) -> int:\n",
    "        customer = 0\n",
    "        values = [0]\n",
    "        i = 0\n",
    "        while i<len(customers) or customer!=0:\n",
    "            if i<len(customers):\n",
    "                customer+=customers[i]\n",
    "            take = min(4,customer)\n",
    "            customer -= take\n",
    "            if i==0:\n",
    "                values[i]=boardingCost*take-runningCost\n",
    "            else:\n",
    "                values.append(values[i-1]+boardingCost*take-runningCost)\n",
    "            i+=1\n",
    "        maxValue = max(values)\n",
    "        if maxValue>0:\n",
    "            k = values.index(maxValue)+1\n",
    "        else:\n",
    "            k = -1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:\n",
    "        if runningCost>=boardingCost*4:\n",
    "            return -1\n",
    "        n=len(customers)\n",
    "        profit=[]\n",
    "        cp=0\n",
    "        for i in range(n-1):\n",
    "            cp-=runningCost\n",
    "            if customers[i]>4:\n",
    "                customers[i+1]+=customers[i]-4\n",
    "                customers[i]=4\n",
    "            cp+=customers[i]*boardingCost\n",
    "            profit.append(cp)\n",
    "        leftc=customers[n-1]\n",
    "        while leftc>0:\n",
    "            cp-=runningCost\n",
    "            if leftc<=4:               \n",
    "                cp+=leftc*boardingCost\n",
    "                profit.append(cp)\n",
    "                leftc=0\n",
    "            else:\n",
    "                leftc-=4               \n",
    "                cp+=4*boardingCost\n",
    "                profit.append(cp)\n",
    "               \n",
    "        mp=max(profit)\n",
    "        # print(profit)\n",
    "        if mp<=0:\n",
    "            return -1\n",
    "        return profit.index(mp)+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsMaxProfit(self, customers: List[int], \n",
    "        boardingCost: int, runningCost: int) -> int:\n",
    "        if runningCost > boardingCost * 4:\n",
    "            return -1\n",
    "        ans_lst = []\n",
    "        profit_now = 0\n",
    "        all_profit = []\n",
    "        rest_cust_num = 0\n",
    "\n",
    "        for cust_num in customers:\n",
    "            tot_cust = cust_num + rest_cust_num\n",
    "            if tot_cust >= 4:\n",
    "                profit_now += 4 * boardingCost - runningCost\n",
    "                rest_cust_num = tot_cust - 4\n",
    "            else:\n",
    "                profit_now += tot_cust * boardingCost - runningCost\n",
    "                rest_cust_num = 0\n",
    "            all_profit.append(profit_now)\n",
    "        \n",
    "        while rest_cust_num > 0:\n",
    "            if rest_cust_num >= 4:\n",
    "                profit_now += 4 * boardingCost - runningCost\n",
    "                rest_cust_num -= 4\n",
    "            else:\n",
    "                profit_now += rest_cust_num * boardingCost - runningCost\n",
    "                rest_cust_num = 0\n",
    "\n",
    "            all_profit.append(profit_now)\n",
    "        max_profit = max(all_profit)\n",
    "        #print(all_profit)\n",
    "        if max_profit <= 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return all_profit.index(max_profit) + 1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
